typedef int ElemType;

void InsertSort(ElemType A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int tmp = A[i];

        for (int j = i - 1; j >= 0; j--)
        {
            if (tmp < A[j])
            {
                A[j + 1] = A[j];
            }
            else
            {
                A[j + 1] = tmp;
                break;
            }
        }
    }
}

void BinaryInsertSort(ElemType A[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int tmp = A[i];

        // binary search
        int low = 0;
        int high = i - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (A[mid] > tmp)
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (int j = i; j - high > 0; j--)
        {
            A[j] = A[j - 1];
        }
        A[high + 1] = tmp;
    }
}